package com.yun.algorithm.dynamicprogramming;

import java.util.Arrays;
import java.util.stream.Collectors;

/**
 * 动态规划
 * 旅行家问题
 * d(出发城市,剩余城市集合)==>从出发城市开始，走完剩余城市，花费的最少代价
 * d(0,1|2|3)=>g[0][1]+d(1,2|3)
 * g[1][3]+d(3,2)
 * =>g[3][2]+d(2,空)
 * g[2][0]
 * <p>
 * g[0][3]+d(3,1|2)
 * g[0][2]+d(2,1|3)
 * 出发城市 i
 * 剩余城市集合 j
 * 遍历j时的变量k（剩余的某一个城市）
 * d(i,j)=>min(
 * g[i][k]+d(k,j去掉k)
 * g[i][k]+d(k,j去掉k)
 * g[i][k]+d(k,j去掉k)
 * )
 * d(k,空)=>从k回到起点=>g[k][i]
 */
public class TravellingSalesmanProblem {
    public static void main(String[] args) {
        int[][] graph = {
                {0, 1, 2, 3},
                {1, 0, 6, 4},
                {2, 6, 0, 5},
                {3, 4, 5, 0},
        };
        System.out.println(tsp(graph));
    }

    private static int tsp(int[][] g) {
        int m = g.length;//城市数目
        int n = 1 << (m - 1);//剩余城市的组合数 2^(m-1)
        int[][] dp = new int[m][n];

        //填充第0列
        for (int k = 0; k < m; k++) {
            dp[k][0] = g[k][0];
        }
        print(dp);

        //填充后续列
        for (int j = 1; j < n; j++) {
            for (int i = 0; i < m; i++) {
                dp[i][j] = Integer.MAX_VALUE >> 1;
                if (contains(j, i)) continue;
                //填充单元格
                for (int k = 0; k < m; k++) {
                    if (contains(j, k)) {
                        dp[i][j] = Integer.min(dp[i][j], g[i][k] + dp[k][exclude(j, k)]);
                    }
                }
            }
        }
        print(dp);
        return dp[0][n - 1];
    }

    static boolean contains(int set, int city) {
        return (set >> (city - 1) & 1) == 1;
    }

    static int exclude(int set, int city) {
        return set ^ (1 << (city - 1));
    }

    static void print(int[][] dist) {
        System.out.println("-------------------------");
        for (int[] row : dist) {
            System.out.println(Arrays.stream(row).boxed()
                    .map(x -> x >= Integer.MAX_VALUE / 2 ? "∞" : String.valueOf(x))
                    .map(s -> String.format("%2s", s))
                    .collect(Collectors.joining(",", "[", "]")));
        }
    }
}

